CMU 15-112 Summer 2019: Fundamentals of Programming and Computer Science
Homework 8 (Due Tue 11-Jun, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.


• To start:
  1. Create a folder named 'week4'
  2. Create hw8.py using Pyzo
  3. When you are ready, submit hw8.py to Autolab. For this hw you will have 20 submissions.
• This homework is partially autograded. You will receive feedback for some of the problems after the deadline.
• Do not use recursion in this assignment.
• Do not hardcode the test cases in your solutions.
• This homework may be graded for style.

1. Big-O Calculation [36pts] [manually graded]
   In a triple-quoted string at the top of your file (just below your name), include solutions to this exercise. For each of the following functions:
   
   
   1. State in just a few words what it does in general.
   2. Write the Big-O time or number of loops for each line of the program, then state the resulting Big-O of the whole program.
   3. Provide an equivalent Python function that is more than a constant-factor faster (so its worst-case Big-O runtime is in a different function family). The better your solution's Big-O runtime, the more points you get!
   4. Write the Big-O time or number of loops for each line of the new program, then state the resulting Big-O of the whole program.
   5. You do not need to write test cases for your faster implementations - we will be grading this problem manually, so we will take a look to see if your new function is correct
   
   

   def slow1(lst): # N is the length of the list lst
       assert(len(lst) >= 2)
       a = lst.pop()
       b = lst.pop(0)
       lst.insert(0, a)
       lst.append(b)
   
   def slow2(lst): # N is the length of the list lst
       counter = 0
       for i in range(len(lst)):
           if lst[i] not in lst[:i]:
               counter += 1
       return counter
   
   import string
   def slow3(s): # N is the length of the string s
       maxLetter = ""
       maxCount = 0
       for c in s:
           for letter in string.ascii_lowercase:
               if c == letter:
                   if s.count(c) > maxCount or \
                      s.count(c) == maxCount and c < maxLetter:
                       maxCount = s.count(c)
                       maxLetter = c
       return maxLetter
   




2. invertDictionary(d) [40 pts] [autograded]
   Write the function invertDictionary(d) that takes a dictionary d that maps keys to values and returns a dictionary of its inverse, that maps the original values back to their keys. One complication: there can be duplicate values in the original dictionary. That is, there can be keys k1 and k2 such that (d[k1] == v) and (d[k2] == v) for the same value v. For this reason, we will in fact map values back to the set of keys that originally mapped to them. So, for example:

   assert(invertDictionary({1:2, 2:3, 3:4, 5:3}) ==
          {2:set([1]), 3:set([2,5]), 4:set([3])})
   

   Also, you may assume that the values in the original dictionary are all immutable, so that they are legal keys in the resulting inverted dictionary.


3. largestSumOfPairs(a) [24 pts] [autograded]
   Write the function largestSumOfPairs(a) that takes a list of integers, and returns the largest sum of any two elements in that list, or None if the list is of size 1 or smaller. So, largestSumOfPairs([8,4,2,8]) returns the largest of (8+4), (8+2), (8+8), (4+2), (4+8), and (2+8), or 16.
   
   Note on runtime: Your function must run in O(n) time. The brute force solution is to try every possible pair of numbers in the list. This runs in O(n**2) time and is much too slow. Another solution might involve sorting. Sorting runs in O(nlogn) times and is also too slow.
   
   Note on autograding: The autograder will sometimes tell you your solution is too slow. However it may not catch all solutions that are too slow (particularly ones that sort using builtins). The running time of your code will be checked manually after the deadline by TAs.